<html>

<head>
  <meta http-equiv="Content-Type" content="text/html; charset=utf-8"> 
  <link rel="stylesheet" title="Default" href="http://acm.math.spbu.ru/~sk1/colorer/my.css">

  <script src="http://acm.math.spbu.ru/~sk1/colorer/highlight.js"></script>
  <script src="http://acm.math.spbu.ru/~sk1/colorer/cpp.js"></script>
  <script>hljs.initHighlightingOnLoad();</script>
</head>

<body>

<pre><code>
import java.util.*;
import java.io.*;

public class carwash_as implements Runnable {
    class Car {
        int i;
        long a;
        long b;
        long sa;
        long sb;

        Car(int i, long a, long b) {
            this.i = i;
            this.a = a;
            this.b = b;
            sa = -1;
            sb = -1;
        }
    }

    public void solve() throws IOException {
        Scanner in = new Scanner(new File("carwash.in"));
        PrintWriter out = new PrintWriter("carwash.out");

        int n = in.nextInt();
        Car[] cars = new Car[n];
        for (int i = 0; i &lt; n; i++) {
            cars[i] = new Car(i, in.nextInt(), in.nextInt());
        }

        Car l = new Car(-1, 0, 0);
        Car r = new Car(-1, 0, 0);
        ArrayList&lt;Car&gt; left = new ArrayList&lt;Car&gt;();
        ArrayList&lt;Car&gt; right = new ArrayList&lt;Car&gt;();
        long ta = 0;
        long tb = 0;
        for (int i = 0; i &lt; n; i++) {
            ta += cars[i].a;
            tb += cars[i].b;

            if (cars[i].a &gt;= cars[i].b) {
                if (cars[i].a &gt;= r.b) {
                    right.add(r);
                    r = cars[i];
                } else {
                    right.add(cars[i]);
                }
            } else {
                if (cars[i].b &gt;= l.a) {
                    left.add(l);
                    l = cars[i];
                } else {
                    left.add(cars[i]);
                }
            }
        }

        Collections.reverse(left);
        ArrayList&lt;Car&gt; a = new ArrayList&lt;Car&gt;();
        ArrayList&lt;Car&gt; b = new ArrayList&lt;Car&gt;();
        a.addAll(left);
        b.addAll(left);
        a.addAll(right);
        b.addAll(right);
        if (ta - l.a &lt; tb - r.b) {
            a.add(r);
            a.add(l);
            b.add(0, l);
            b.add(r);
        } else {
            a.add(0, l);
            a.add(r);
            b.add(0, r);
            b.add(1, l);
        }

        int ai = 0;
        int bi = 0;
        long cta = 0;
        long ctb = 0;
        while (ai &lt; a.size() || bi &lt; b.size()) {
            if ((cta &lt;= ctb && ai &lt; a.size()) || bi == b.size()) {
                Car prb = bi == 0 ? null : b.get(bi - 1);
                Car cra = a.get(ai);
                if (prb == null || prb.i != cra.i || cta &gt; ctb) {
                    cra.sa = cta;
                } else {
                    cra.sa = ctb;
                }
                cta = cra.sa + cra.a;
                ai++;
            } else {
                Car pra = ai == 0 ? null : a.get(ai - 1);
                Car crb = b.get(bi);
                if (pra == null || pra.i != crb.i || ctb &gt; cta) {
                    crb.sb = ctb;
                } else {
                    crb.sb = cta;
                }
                ctb = crb.sb + crb.b;
                bi++;
            }
        }

        out.println(Math.max(cta, ctb));
        for (int i = 0; i &lt; n; i++) {
            out.println(cars[i].sa + " " + cars[i].sb);
        }

        in.close();
        out.close();
    }

    public void run() {
        try {
            solve();
        } catch (IOException e) {
        }
    }

    public static void main(String[] arg) {
        new Thread(new carwash_as()).start();
    }
}
</code></pre>

</body>
</html>

<font style="visibility:hidden">
